package demo1;

import java.util.*;

public class Solution {

    //1.剑指 Offer 57 - II. 和为s的连续正数序列(滑动窗口)
    public int[][] findContinuousSequence(int target) {
        if(target <= 2) {
            return new int[][]{new int[0]};
        }
        List<int[]> list = new ArrayList<>();
        int left = 1;
        int right = 2;
        int sum = 3;
        while (right <= target / 2 + 1) {
            if(sum == target) { //一种可能
                int[] tmp = new int[right - left + 1];
                int index = 0;
                for(int i = left; i <= right; i++) {
                    tmp[index++] = i;
                }
                list.add(tmp);
                sum -= left;
                left++;
                right++;
                sum += right;
            } else if(sum < target) {
                right++;
                sum += right;
            } else {
                sum -= left;
                left++;
            }
        }
        //放入矩阵
        int[][] ret = new int[list.size()][];
        for(int i = 0; i < list.size(); i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }

    //2.剑指 Offer 15. 二进制中1的个数
    public int hammingWeight(int n) {
        int count = 0;
        for(int i = 0; i < 32; i++) {
            if((n & 1) == 1) {
                count++;
            }
            n >>= 1;
        }
        return count;
    }

//    //3.剑指 Offer 64. 求1+2+…+n(短路原理)
//    public int sumNums(int n) {
//        int sum = n;
//        boolean flag = (sum >= 1) && (sum += sumNums(n - 1)) >= -1;
//        return sum;
//    }

    //剑指 Offer 64. 求1+2+…+n(try catch骚解)
    public int sumNums(int n) {
        try {
            int ans = 1 % n;
        } catch (Exception e) {
            return 0;
        }
        return sumNums(n - 1) + n;
    }
//
//    //剑指 Offer 59 - I. 滑动窗口的最大值(优先级队列)
//    public int[] maxSlidingWindow(int[] nums, int k) {
//        int len = nums.length;
//        int retLen = len - k + 1;
//        int[] ret = new int[retLen];
//        int index = 0;//ret的下标
//        //滑动窗口
//        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2 - o1;
//            }
//        });
//        //开始滑动
//        for(int i = 0; i < nums.length; i++) {
//            if(queue.size() < k) {
//                queue.offer(nums[i]);
//            } else {
//                queue.remove(nums[i - k]);
//                queue.offer(nums[i]);
//            }
//            if(queue.size() == k) {
//                ret[index++] = queue.peek();
//            }
//        }
//        return ret;
//    }

    //4.剑指 Offer 59 - I. 滑动窗口的最大值(模拟单调队列)
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int retLen = len - k + 1;
        int[] ret = new int[retLen];
        int index = 0;//ret的下标
        //滑动窗口
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 0; i < nums.length; i++) {
            if(i < k) {
                while(!deque.isEmpty() && nums[i] > deque.getLast()) {
                    deque.pollLast();
                }
                deque.addLast(nums[i]);
            } else {
                while(!deque.isEmpty() && nums[i] > deque.getLast()) {
                    deque.pollLast();
                }
                deque.addLast(nums[i]);
                if(deque.getFirst() == nums[i - k]) {
                    deque.pollFirst();
                }
            }
            if(i + 1 >= k) {
                ret[index++] = deque.getFirst();
            }
        }
        return ret;
    }

    //5.面试题61. 扑克牌中的顺子(排序)
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int count = 0;//记录扑克牌中0的个数
        for(int i = 0; i < nums.length - 1; i++) {
            if(nums[i] == 0) {
                count++;
            } else if(nums[i] == nums[i + 1]) {
                return false;
            } else if(nums[i + 1] - 1 != nums[i]) {
                count = count - (nums[i + 1] - nums[i]) + 1;
            }
        }
        return count >= 0;
    }

    //6.剑指 Offer 17. 打印从1到最大的n位数(数学)
    public int[] printNumbers(int n) {
        int ans = (int)Math.pow(10, n);
        int[] arr = new int[ans - 1];
        for(int i = 1; i < ans; i++) {
            arr[i - 1] = i;
        }
        return arr;
    }
//
//    //剑指 Offer 39. 数组中出现次数超过一半的数字(getOrDefault)
//    public int majorityElement(int[] nums) {
//        HashMap<Integer, Integer> map = new HashMap<>();
//        for(int i = 0; i < nums.length; i++) {
//            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
//            if(map.get(nums[i]) > nums.length / 2) {
//                return nums[i];
//            }
//        }
//        return -1;
//    }

    //剑指 Offer 39. 数组中出现次数超过一半的数字(极限一换一)
    public int majorityElement(int[] nums) {
        int ret = 0;
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            if(count == 0) {
                ret = nums[i];
                count++;
            }
            count = ret == nums[i] ? count + 1 : count - 1;
        }
        return ret;
    }
//
//    //7.剑指 Offer 56 - I. 数组中数字出现的次数(空间O(n))
//    public int[] singleNumbers(int[] nums) {
//        Set<Integer> set = new HashSet<>();
//        for(int i = 0; i < nums.length; i++) {
//            if(!set.contains(nums[i])) {
//                set.add(nums[i]);
//            } else {
//                set.remove(nums[i]);
//            }
//        }
//        int[] ret = new int[2];
//        int index = 0;
//        for(int num : set) {
//            ret[index++] = num;
//        }
//        return ret;
//    }

    //剑指 Offer 56 - I. 数组中两个只出现一次的数(位运算,时间O(n)空间O(1))
    public int[] singleNumbers(int[] nums) {
        int ans = 0;//保存两个只出现一次的数的异或结果
        for(int num : nums) {
            ans ^= num;
        }
        //找出这两个数第一个出现1的位(
        // 因为异或就是不同位才为1，因此找到这个1就可以把这两个数分成两组，另外也会将相同数分成两组)
        int target = 1;
        while ((ans & target) == 0) {
            target <<= 1;
        }
        //分组
        int[] arr = new int[2];
        for(int num : nums) {
            if((num & target) == 0) {//这里为什么是等于0，而不是1？因为为了区分那两个不相同的数，肯定会有一个结果是0，另一个数结果未知
                arr[0] ^= num;
            } else {
                arr[1] ^= num;
            }
        }
        return arr;
    }
//
//    //8.剑指 Offer 57. 和为s的两个数字(set)
//    public int[] twoSum(int[] nums, int target) {
//        Set<Integer> set = new HashSet<>();
//        int[] arr = new int[2];
//        for(int i = 0; i < nums.length; i++) {
//            if(set.contains(target - nums[i])) {
//                arr[0] = nums[i];
//                arr[1] = target - nums[i];
//                break;
//            }
//            set.add(nums[i]);
//        }
//        return arr;
//    }

    //8.剑指 Offer 57. 和为s的两个数字(双指针)
    public int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int[] arr = new int[2];
        while(left < right) {
            int sum = nums[left] + nums[right];
            if(sum == target) {
                arr[0] = nums[left];
                arr[1] = nums[right];
                break;
            } else if(sum > target) {
                right--;
            } else {
                left++;
            }
        }
        return arr;
    }

    //9.剑指 Offer 51. 数组中的逆序对(归并排序)
    private int count;
    public int reversePairs(int[] nums) {
        mergeFun(nums, 0, nums.length - 1);
        return count;
    }

    private void mergeFun(int[] nums, int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeFun(nums, left, mid);
        mergeFun(nums, mid + 1, right);
        merge(nums, left, right, mid);
    }

    private void merge(int[] nums, int left, int right, int mid) {
        int[] tmpArr = new int[right - left + 1];
        int index = 0;//tmpArr的下标
        int s1 = left;
        int s2 = mid + 1;
        while(s1 <= mid && s2 <= right) {
            if(nums[s1] <= nums[s2]) {
                tmpArr[index++] = nums[s1++];
            } else {
                tmpArr[index++] = nums[s2++];
                count += mid - s1 + 1;
            }
        }
        while(s1 <= mid) {
            tmpArr[index++] = nums[s1++];
        }
        while(s2 <= mid) {
            tmpArr[index++] = nums[s2++];
        }
        //合并
        for(int i = 0; i < index; i++) {
            nums[i + left] = tmpArr[i];
        }
    }

}

//10.面试题59 - II. 队列的最大值(单调队列 + 普通队列)
class MaxQueue {

    //单调队列
    private Deque<Integer> deque = null;
    //普通队列
    private Queue<Integer> queue = null;

    public MaxQueue() {
        this.deque = new ArrayDeque<>();
        this.queue = new LinkedList<>();
    }

    public int max_value() {
        return deque.isEmpty() ? -1 : deque.peekFirst();
    }

    public void push_back(int value) {
        if(deque.isEmpty()) {
            deque.offer(value);
        } else {
            while(!deque.isEmpty() && deque.getLast() < value) {
                deque.pollLast();
            }
            deque.offerLast(value);
        }
        queue.offer(value);
    }

    public int pop_front() {
        if(deque.contains(queue.peek())) {
            deque.remove(queue.peek());
        }
        return queue.isEmpty() ? -1 : queue.poll();
    }

}

class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.reversePairs(new int[]{7,5,6,4});
    }
}